机器学习基础

验证集与测试集

  • 验证集的作用：

    使用验证集是为了 快速调参，也就是用验证集选择超参数（网络层数，网络节点数，迭代次数，学习率这些）。另外用验证集还可以监控模型是否异常（过拟合啦什么的），然后决定是不是要提前停止训练。

    验证集的关键在于 选择超参数，我们手动调参是为了让模型在验证集上的表现越来越好，如果把测试集作为验证集，调参去拟合测试集，就有点像作弊了。

  • 而测试集既 不参与参数的学习过程，也 不参与参数的选择过程，仅仅用于模型评价。

Bias 与 Variance

欠拟合也称为高偏差（bias），过拟合也称为高方差（variance）。

关于过拟合问题，要注意：

Batch Normalization的主要作用是加快网络的训练速度，一般不说它是防止过拟合的。

如果硬要说是防止过拟合，可以这样理解：

BN每次的mini-batch的数据都不一样，但是每次的mini-batch的数据都会对moving mean和moving variance产生作用，可以认为是引入了噪声，这就可以认为是进行了data augmentation，而data augmentation被认为是防止过拟合的一种方法。因此，可以认为用BN可以防止过拟合。

梯度下降

神经网络的核心思想就是通过调整参数w和b，来尽可能地最小化损失函数，解决这个问题的方法就是梯度下降法。

  • 直观理解：

    ⾸先把我们的函数想象成⼀个⼭⾕。我们想象有⼀个⼩球从⼭⾕的斜坡滚落下来。我们的⽇常经验告诉我们这个球最终会沿着最陡峭的方向滚到⾕底。

    我们会为⼀个（假想的）球体随机选择⼀个起始位置，然后模拟球体滚落到⾕底的运动。这其实就是梯度下降法的核心思想。我们可以通过计算 C 的导数（或者⼆阶导数）来简单模拟——这些导数会告诉我们⼭⾕中局部“形状”的⼀切，由此知道我们的球将怎样滚动。

    我们知道梯度指向的是某一点处方向导数最大的方向，也就是最陡峭的方向。

对于凸优化问题，梯度下降法一定能找到全局最优点，但非凸函数则不一定，可能会陷入局部最优。

极大似然估计与贝叶斯估计

贝叶斯估计

  • 全概率公式：设事件 [公式] 构成一个完备事件组，即它们两两不相容，和为全集且 [公式] ，则对任一事件 [公式] 有：

[公式]

​ 可以看出，全概率公式是“由因推果”的思想，当知道某件事的原因后，推断由某个原因导致这件事发生的概率为多少。

  • 贝叶斯公式：符号定义与全概率公式相同，则：

[公式]

​ 可以看出，贝叶斯公式是“由果溯因”的思想，当知道某件事的结果后，由结果推断这件事是由各个原因导致的概率为多少。

  • 先验概率（prior probability）：指根据以往经验和分析，在实验或采样前就可以得到的概率，如上式中的 $P(B_i)$。

  • 后验概率（posterior probability）：指某件事 $A$ 已经发生，想要计算这件事发生的原因是由某个因素引起的概率。

    可以看出，先验概率就是事先可估计的概率分布，而后验概率类似贝叶斯公式“由果溯因”的思想。

极大似然估计

参考这篇文章。

  • 似然函数：

    似然性（likelihood）与概率（possibility）同样可以表示事件发生的可能性大小，但是二者有着很大的区别：

    • 条件概率 [公式] 是在已知参数 [公式] 的情况下，发生观测结果 [公式] 可能性大小；
    • 似然函数 [公式] 则是从观测结果 [公式] 出发，分布函数的参数为 [公式] 的可能性大小；

    这里可能不是那么好理解，我们再详细说明下，似然函数如下：

    [公式]

    其中 [公式] 已知， [公式] 未知。若对于两个参数 [公式] , [公式] ，有

    [公式]

    那么意味着当 [公式] 时，随机变量 [公式] 生成 [公式] 的概率大于当参数 [公式] 时。

    这也正是似然的意义所在，若观测数据为 [公式] ，那么 [公式] 是比 [公式] 更有可能为分布函数的参数。

  • 最大似然估计：

    • 对于给定样本值，使似然函数 $L$ 达到最大值的参数值 $\theta^*$ 称为未知参数 $\theta$ 的最大似然估计值。

    • 最大似然估计的思想在于，对于给定的观测数据 [公式] ，我们希望能从所有的参数 [公式] 中找出能最大概率生成观测数据的参数 [公式] 作为估计结果，因此被估计出的参数 [公式] 应该满足：

    [公式]

    • 最大化的步骤是通过对未知参数求偏导（即求极值），并令其等于0来解得。

二者的区别

从贝叶斯公式的数学表达就可以看到，贝叶斯估计引入了先验概率，通过先验概率与似然概率来求解后验概率，而最大似然估计是直接通过最大化似然函数（条件概率）来求解得出的。

  • 我们举例来说明：

    假设某人感染了新冠病毒，那么其核酸检测呈阳性的概率为 95%；如果未感染病毒，则阳性的概率为 1%。现在有一个人结果为阳性，问这个人感染病毒了吗？

  • 极大似然估计：

    既然感染了病毒出现阳性的概率为95%，没感染出现阳性的概率只有1%，本着谁大像谁的原则，那我们认为这个人已经感染了病毒。

  • 贝叶斯估计：

    首先我们必须知道先验概率，即整个人群中感染此病毒的人数为10%左右，那么由贝叶斯公式：

    $$P(感染|核酸检测阳性) = \frac{P(核酸检测为阳性且感染了新冠病毒)}{P(核酸检测阳性)} = \frac{P(感染) P(阳性|感染)}{P(感染) P(阳性|感染) + P(未感染) P(阳性|未感染)} = \frac{0.1 \times 0.95}{0.1 \times 0.95 + 0.9 \times 0.01} = 0.51$$

    即当检测呈阳性时，几乎是只有一半概率能确信其感染了新冠病毒（只是随便举的数据）。

从本质上来说，最大似然是对点估计，贝叶斯推断是对分布估计。即最大似然是求出最有可能的 $\theta$ 值，而贝叶斯推断则是求解 $\theta$ 的分布。

二者的联系

当先验分布是均匀分布时，取后验概率最大，就能从贝叶斯估计得到极大似然估计，即二者等价：

$$\hat{P}(\theta | D) = \frac{P(\theta)P(D|\theta)}{P(D)} = \frac{P(\theta)P(D|\theta)}{\sum_i P(\theta_i)P(D|\theta_i)} = \frac{P(D|\theta)}{\sum_i P(D|\theta_i)} = \frac{P(D|\theta)}{C}$$

最小二乘法

参考这里 。

定义

最小二乘法也被称作最小平方法，是一种求解矩阵方程参数的算法。

假设对于一个二维空间中，有这么一些点是呈现线性关系的：

img

我们希望用一个线性模型（函数） [公式] 表示上面的关系。最小二乘法就是试图找到一条直线（即确定a，b），使得所有样本到直线上的欧式距离之和最小，亦即误差最小：

[公式]

这便是最小二乘法了。为什么叫二乘法？因为是最小化平方和。

求解步骤

最小二乘法的步骤：对 $\theta$ 求偏导，让偏导等于0，求出 $\theta$ 值。

最小二乘法与最大似然估计的区别与联系

最大似然估计和最小二乘法怎么理解？

  • 最小二乘法要在很多条线中间选择出一条距离所有的样本点的欧氏距离之和最小的，即误差最小的直线。
  • 最大似然估计是选择一个能最大概率生成观测数据的参数 [公式] 作为估计结果；做法是把我们观察到每个样本的概率乘到一起，然后试图调整参数以最大化这个概率的乘积。

关于损失函数

交叉熵损失函数

交叉熵损失函数原理详解

交叉熵是信息论中的一个重要概念，主要用于度量两个概率分布间的差异性，要理解交叉熵，需要先了解下面几个概念。

信息量

信息奠基人香农（Shannon）认为“信息是用来消除随机不确定性的东西”，也就是说衡量信息量的大小就是看这个信息消除不确定性的程度。

  • “太阳从东边升起”，这条信息并没有减少不确定性，因为太阳肯定是从东边升起的，这是一句废话，信息量为0。

  • ”2018年中国队成功进入世界杯“，从直觉上来看，这句话具有很大的信息量。因为中国队进入世界杯的不确定性因素很大，而这句话消除了进入世界杯的不确定性，所以按照定义，这句话的信息量很大。

根据上述可总结如下：信息量的大小与信息发生的概率成反比。概率越大，信息量越小。概率越小，信息量越大。

设某一事件发生的概率为P(x)，其信息量表示为：

$$I(x) = - log(P(x))$$

其中，$I(x)$ 表示信息量，log表示以e为底的自然对数。

信息熵

信息熵也被称为熵，用来表示所有信息量的期望。期望是试验中每次可能结果的概率乘以其结果的总和。

所以信息量的熵可表示为：

$$H(X) = - \sum^n_{i=1} P(x_i) log(P(x_i))$$

其中， $X$ 是一个离散型随机变量，且有 $X = x_1, x_2, \dots, x_n$

相对熵（KL散度）

如果对于同一个随机变量 $X$ 有两个单独的概率分布 $P(x)$ 和 $Q(x)$，则我们可以使用KL散度来衡量这两个概率分布之间的差异。

下面直接列出公式，再举例子加以说明。

$$D_{KL} (p || q) = \sum^n_{i=1} p(x_i) log(\frac{p(x_i)}{q(x_i)})$$

在机器学习中，常常使用 $P\left(x\right)$ 来表示样本的真实分布，$Q \left(x\right)$ 来表示模型所预测的分布。KL散度越小，表示 $P(x)$ 与 $Q(x)$ 的分布越接近，可以通过反复训练迭代来使 $Q(x)$ 的分布更加接近真实分布 $P(x)$ 。

交叉熵

首先将KL散度公式拆开：

$$D_{KL} (p || q) = \sum^n_{i=1} p(x_i) log(\frac{p(x_i)}{q(x_i)}) \ = \sum^n_{i=1} p(x_i) log(p(x_i)) - \sum^n_{i=1} p(x_i) log(q(x_i)) \ = - H(p(x)) + [-\sum^n_{i=1} p(x_i) log(q(x_i))] $$

前者 $H \left (p \left (x \right)\right)$ 表示信息熵，后者即为交叉熵，KL散度 = 交叉熵 - 信息熵。

所以交叉熵公式表示为：

$$H(p, q) = -\sum^n_{i=1} p(x_i) log(q(x_i))$$

在机器学习训练网络时，输入数据与标签常常已经确定，那么真实概率分布 $P\left(x \right)$ 也就确定下来了，所以信息熵在这里就是一个常量。由于KL散度的值表示真实概率分布 $P\left(x\right)$ 与预测概率分布 $Q \left(x\right)$ 之间的差异，值越小表示预测的结果越好，所以需要最小化KL散度，而交叉熵等于KL散度加上一个常量（信息熵），且公式相比KL散度更加容易计算，所以在机器学习中常常使用交叉熵损失函数来计算loss就行了。

总结

  • 交叉熵能够衡量同一个随机变量中的两个不同概率分布的差异程度，在机器学习中就表示为真实概率分布与预测概率分布之间的差异。交叉熵的值越小，模型预测效果就越好。
  • 交叉熵在分类问题中常常与softmax是标配（tf.cross_entropy_with_softmax），首先利用softmax处理输出的结果，使其多个分类的预测值和为1，再通过交叉熵来计算损失。

MAE与MSE的区别

6.1号字节二面问到的问题，让我从梯度的方向考虑，当时没答出来。晚上突然意识到自己把这个很重要的公式搞忘掉了：

$$w = w - \eta J(w)$$

我当时以为MAE求导后梯度是个常数值，参数就不会更新了。。。当时脑子可能有点不太清醒。。。

实际上，正由于MAE求导后梯度是个常数值，所以参数每次更新的大小都相同。也就是说，即使损失值很小，梯度也很大，这就不利于模型的学习。

而MSE的梯度，求完导后还是个一阶函数，所以梯度会越来越小，每次更新的大小也会越来越小。

经典算法题

100层楼扔鸡蛋，确定鸡蛋摔碎的楼层N

【题目】

某栋大楼有100层。若将鸡蛋从第N层或更高的楼层扔下来，鸡蛋就会摔碎，而从第N层以下的楼层扔下鸡蛋不会摔碎。

现在给你两个鸡蛋，请找出N，并要求最差情况下扔鸡蛋次数最少。

【分析】

刚拿到这个题目我以为是二分法的变式，于是考虑第一次从50层扔鸡蛋，有两种情况：

  1. 如果鸡蛋摔碎了，说明 N <= 50，且由于你只剩下一个鸡蛋了，所以只能从1~49层开始一层层扔鸡蛋测试，最坏需要49次，加上在50层扔的第一个鸡蛋，最坏需要50次测试；
  2. 如果鸡蛋没有碎，说明 N > 50，而且你还有两个鸡蛋，可以接着在51~100层内二分，那这时候最坏情况是多少呢？可以想见，最坏是25次。

因此，如果从第50层开始扔，最差情况下需要50次。

那么最好情况呢？就是如果每次测试鸡蛋都没碎，因为每次范围缩小一半，所以最多需要 log100 次，大约是7次。这说明每次缩小一半区间太大了，如果想让最差情况下测试次数最少，就要尽可能地均衡最差情况与最好情况。

所以我们尝试把区间缩小，不妨从第10层开始扔鸡蛋，然后是20层，30层，…，100层：

  • 如果鸡蛋在第10层就碎了，那么按照上面的分析，最坏情况需要测试10次。

  • 如果鸡蛋在第100层才碎（不可能不碎哈），那说明N在91~100之间，由于在10，20，…,100都扔了鸡蛋，所以“最好”情况为10+9=19次

因此，最差情况为19次，显然我们放缩得太多了，那到底该如何确定每次选择的楼层呢？

按照前面的分析，我们知道，要想最差情况下扔鸡蛋次数最少，需要尽可能地均衡最差情况与最好情况，即让两种情况下的测试次数尽可能相同。

【解法1】

不妨设第一次扔的楼层为x，第二次扔的楼层为y，讨论第一次扔鸡蛋的情况：

  • 如果鸡蛋在x层碎了，那么只能挨个测试1~x-1层，共需测试 $x$ 次；
  • 如果鸡蛋在x层没碎，则要在第y层继续测试，此时又会出现两种情况（碎或不碎），但实际上，我们只想要最差情况下需要测试几次，而最差情况肯定是在第y层摔碎了，所以需要从x+1层到y-1层挨个扔鸡蛋测试。再加上第x层和第y层扔的两次（即可以理解为从第x层到第y层均做了测试），总共就是 $y-x+1$ 次。

令两种情况相等，即 $x = y-x+1$ ，亦即 $y = 2x - 1$ 。因此第一次扔和第二次扔相差 $y - x$ ，也就是 $x - 1$ 层。

依此类推，假设第三次扔的楼层为z，讨论第二次扔鸡蛋的情况：

这里务必要注意与第一次扔的区别：第一次扔时起始楼层是1，第二次扔时起始楼层是x+1而非x，因为x已经测试过了，这就会导致之后在扔时都会比前一次少个1。举个例子：

  • 比如第一次在第x=10层扔，鸡蛋碎了，那么需要从第1层开始测试，直到第9层，因此总共需要1+9=10次；
  • 根据上面讨论，第二次将在 2x-1 = 19层测试，如果鸡蛋碎了，说明N在11~19层之间。因此需要从第11层开始扔，直到第18层，因此总共需要测试1+8=9次。

这就是第一次扔与之后再扔的区别。

  • 第一次在x层扔时如果鸡蛋碎了，是从第1层开始测试，直到x-1层，那么带上第x层扔的就是x次。
  • 而第二次在y层扔时如果鸡蛋碎了，只需从上一次扔的楼层开始测试，而x已经测试过了，因此是从x+1层到y-1层，带上第y层扔的就是 y - (x+1) + 1 = y - x 次。
  • 如果鸡蛋在第y层碎了，那么需要逐个测试x+1~y-1层，再带上第y层扔的一次，总共需测试 1 + (y-1) - (x+1) + 1 = y-x = x-1 次；
  • 如果鸡蛋在第y层没碎，那么需要在第z层继续测试，也就是 $z - y + 1$ 次

因此有 $y - x = z - y + 1$ ，得 $z = 2y - x - 1 = 3x-3$。与上一此扔相差 $z - y$ ，也就是 $x-2$ 层。

依次类推，每次扔的楼层之间相差的层数逐次减1，也就是 x, x-1, x-2 , …, 1。

这就确保了两种情况所需的测试次数是相等的，即保持了均衡。同时为了保证最后一次测试要覆盖100层楼，所以有 $x + (x-1) + (x-2) + \dots + 1 = (x+1)x/2 \geq 100$ ，解得 $x \geq 14$ 。

因此，每次测试的楼层为 14,27,39,50,60,69,77,84,90,95,99,100。

这样就能够保证，如果鸡蛋一直没碎，最后需要测试12次，而在前面无论哪一层碎了，总共都只需要测试14次。

【解法2】

解法1写的过于精细，或者说麻烦了。实际上，当第一次在x层扔时鸡蛋没碎，那么第二次再扔时跟前面1 ~ x层已经没有关系了，相当于以后只需关注从第x+1层到第100层即可，相当于整个大楼的1 ~ x层被移走了，不再要了，只是占了一次测试机会而已。

因为我们目标是让两种情况所需测试次数尽可能相等。

  • 在第x层扔时鸡蛋碎了时需要测试x次，所以我们只要保证当鸡蛋没碎时总共只用测试x次即可，而这时前面已经用掉一次测试机会了，也就是说，从第x+1层开始，我们只能测试x-1次，所以第二次测试应该在(x+1)~(x+x-1)之间进行，即第二次应在 x + x - 1 层扔鸡蛋。
  • 第三次扔时跟前面的 x + x - 1 层已经没关系了，应该从下一层开始， 且因为又用掉了一次机会，第三次只能测试x-2次了。
  • 依次类推，下一次 x-3, x-4, …, 1。

每次扔砍掉底部的楼层，最后就有 $x + (x-1) + (x-2) + \dots + 1 = (x+1)x/2 \geq 100$ ，解得 $x \geq 14$ 。

两种思路的不同之处在于：

  • 解法1是设每次扔的楼层，利用「两种情况测试次数相同」这个我们期望的条件来建立等式关系，进而求得下一层该在哪扔。
  • 解法2则是把这个等式关系作为已知条件，反推出两层扔的楼层之间的间隔差为1。

【拓展】

本问题可以使用动态规划的方法，推广到n层楼，m个鸡蛋。假设 $dp[n, m]$ 表示n层楼、m个鸡蛋时找到最高楼层的最少尝试次数。

  • 当第一个鸡蛋从第i层扔下，如果碎了，还剩下m-1个鸡蛋，且N应该在1~i之间，因此还需要 $dp[i-1,m-1]$ 次，找到子问题；
  • 如果鸡蛋没碎，说明N在i+1~n层之间，因此还需要 $dp[n-i, m]$ 次，得到另一个子问题。

综上，状态转移方程如下：

$$dp[n, m] = min_{i=1,…n} { 1 + max(dp[i-1,m-1], dp[n-i, m]) }$$

问题解决。